/**
 * @author Zou Yu
 * create at: 2022/3/21 17:25
 */

// 整数数组 nums 按升序排列，数组中的值 互不相同 。
// 在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，
// 使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。
// 例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
//
// 输入：nums = [4,5,6,7,0,1,2], target = 0
// 输出：4

/**
 * https://leetcode-cn.com/leetbook/read/binary-search/xeog5j/ <br>
 * 解决方案: <br>
 * 类比前面的旋转数组移到结尾( [4, 5, 6, 7, 1, 2, 3, 4, 5, 6, 7] )，形成递增数组，再通过取余运算取到对应的数值 <br>
 * 缺点：right = 断点下标 + size 可能溢出 <br>
 * eg: [4, 5, 6, 7, 1, 2, 3] size=7 <br>
 * mid = left + (right - left) / 2 <br>
 * 初始条件: left = 4, right = 11 <br>
 * 终止条件：nums[left] > nums[right] <br>
 * 向左查找：right = mid - 1 <br>
 * 向右查找：left = mid + 1 <br>
 */
public class Example_1_2 {
    public int search(int[] nums, int target) {
        if(nums == null || nums.length == 0) {
            return -1;
        }

        // 初始化 left, right, size
        int left = 0;
        int right = nums.length;
        int size = nums.length;

        if (size > 1) {
            int i;
            // 判断是否是旋转排序数组
            for(i = 1; i < nums.length; i++) {
                if(nums[i] < nums[i - 1]) {
                    break;
                }
            }
            if (i < nums.length) {
                // 旋转排序数组，更改 left, right
                left = i;
                right = i + size;
            }
        }

        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(nums[mid % size] == target) { return mid % size; }
            else if(nums[mid % size] < target) { left = mid + 1; }
            else { right = mid - 1; }
        }

        return -1;
    }

    public static void main(String[] args) {
//        int [] nums = {4, 5, 6, 7, 1, 2, 3};
//        int [] nums = {1, 2, 3,  5, 6, 7};
        int [] nums = {4, 5, 1};
//        int target = 8;
//        int target = 1;
//        int target = 2;
        int target = 1;
//        int target = 4;
//        int target = 5;
//        int target = 7;
        Example_1_2 example = new Example_1_2();
        int search = example.search(nums, target);
        System.out.println(search);
    }
}